import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: ${USER}
 * Date: ${YEAR}-${MONTH}-${DAY}
 * Time: ${TIME}
 */
//快慢指针的方式
class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length/2;
        int fast = n;
        int slow = n;
        while (fast < nums.length) {
            if (nums[slow - n] != nums[fast]) {
                fast++;
                slow++;
            } else {
                return nums[fast];
            }
        }
        return 0;

//        官解
//        Arrays.sort(nums);
//        return nums[nums.length / 2];
    }
}
public class Method1 {
    public static void main(String[] args) {
        int[] nums = {2,2,1,1,1,2,2};
        Solution solution = new Solution();
        int n = solution.majorityElement(nums);
        System.out.println(n);
    }
}